package cn.kent;

/**
 * 合并两个升序链表
 */
public class MergeTwoLists {

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode resNode = new ListNode();
        ListNode tmpNode = resNode;
        if (list1 == null && list2 == null) {
            return null;
        }

        // 1. 循环比较排序插入
        while (true) {
            if (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    tmpNode.val = list1.val;
                    list1 = list1.next;
                } else {
                    tmpNode.val = list2.val;
                    list2 = list2.next;
                }
                tmpNode.next = new ListNode();
                tmpNode = tmpNode.next;
            } else if (list1 != null) {
                // 将list1全部放到结果后面
                tmpNode.val = list1.val;
                tmpNode.next = list1.next;
                return resNode;
            } else {
                // 将list1全部放到结果后面
                tmpNode.val = list2.val;
                tmpNode.next = list2.next;
                return resNode;
            }
        }
    }

    /**
     * 递归 - 官方代码
     */
    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists2(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists2(l1, l2.next);
            return l2;
        }
    }


    public static void main(String[] args) {
        // [1,2,4]
        // [1,3,4]
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(2);
        list1.next.next = new ListNode(4);

        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);

        ListNode listNode = mergeTwoLists2(list1, list2);

        System.out.println("遍历结果节点...");
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
